package sortAlgorithm;

public class ShellSort {
	public static void main(String[] args) {
		int[] a = { 9, 6, 4, 3, 1 };
		shellSort(a);
		printArray(a);
	}

	public static void shellSort(int[] array) {
		// 不断地缩小增量
		for (int interval = array.length / 2; interval > 0; interval /= 2) {
			// 一趟一个增量，用增量来分组，组内进行插入排序
			// 插排
			for (int i = interval; i < array.length; i++) {
				int target = array[i];
				int j = i - interval;	//target组内前一个元素
				// 往自己的组里，进行插入排序
				while (j > -1 && array[j] > target) {//前一个元素存在，且大于target
					array[j + interval] = array[j];
					j -= interval;
				}
				array[j + interval] = target;
			}
		}

	}

	public static void printArray(int[] array) {
		System.out.print("[");
		for (int i = 0; i < array.length - 1; i++) {
			System.out.print(array[i] + ",");
		}
		System.out.println(array[array.length - 1] + "]");
	}
}
